//
//  33. 搜索旋转排序数组.swift
//  Top600
//
//  Created by rjb on 2021/7/30.
//

import Foundation
class Solution33 {
    // 整体的思路
    // 可以直接用二分查找
    func search(_ nums: [Int], _ target: Int) -> Int {
        var left = 0
        var right = nums.count - 1
        while left <= right {
            let mid = (left + right) / 2
            if nums[mid] == target {
                return mid
            }
          
            if nums[0] <= nums[mid] {
                // 如果左边是有序的
                if nums[0] <= target && target < nums[mid] {
                    right = mid - 1
                } else {
                    left = mid + 1
                }
            } else {
                // 如果右边是有序的
                if nums[mid] < target && target <= nums[nums.count - 1] {
                    left = mid + 1
                } else {
                    right = mid - 1
                }
            }
        }
        return -1
    }
    static func test() {
        let solution = Solution33()
        let nums =  [4,5,6,7,0,1,2]
        let target = 0
        let result = solution.search(nums, target)
        print(result)
    }
}
